In recent years, there has been interest in offering VPN services over the public Internet. An important goal has been to provide performance guarantees in the VPN context comparable to those associated with private wide-area networks (WANs). The first generation internet protocol (IP) based VPN technology mainly focused on security and tunnel-based routing, but fell short of providing any quality of service (QoS) guarantees. However, the recent emergence of certain IP technologies, such as multiprotocol label switching (MPLS), enhances the Internet infrastructure to provide services suitable for QoS improvements. Thus, the problem of provisioning VPN services with QoS guarantees has become an active area of research.
The “pipe” model and the “hose” model are two popular models for providing QoS in the context of VPNs.
In the pipe model, the VPN customer specifies QoS requirements between every pair of VPN endpoints and each endpoint is connected only to a single other endpoint. Thus, the pipe model requires the customer to know the complete traffic matrix, specifying the traffic load between every pair of endpoints.
However, as the number of endpoints grows and as the connectivity dynamics increase, it may be difficult to achieve bandwidth requirements between the endpoints. Thus, algorithms for establishing VPNs have begun to resort to models with aggregate bandwidth demands, such as the hose model. See, for instance, Duffield et al., “A Flexible Model for Resource Management in Virtual Private Networks,” Proceedings of Association for Computing Machinery (ACM) Special Interest Group on Communications (SIGCOMM) (1998), the disclosure of which is hereby incorporated by reference.
In the hose model, one VPN endpoint can communicate with multiple additional VPN endpoints through a single connection, and each VPN endpoint specifies its aggregate ingress and egress bandwidth requests. The ingress bandwidth for a VPN endpoint specifies the incoming traffic from all the other VPN endpoints into the VPN endpoint, while the egress bandwidth is the amount of traffic the VPN endpoint can send to the other VPN endpoints. The hose model is scalable since the customer manages the allocated bandwidth at per flow basis at the network edge while the VPN provider, which sets up the network, is concerned only with the flow aggregates inside the network.
A problem with the hose model is that failure of an edge within the network can cause multiple VPN endpoints to lose communication. A need therefore exists for restoration techniques for networks that allow a single VPN endpoint to communicate with multiple additional VPN endpoints.